In computer systems, a lock is a synchronization mechanism used to enforce limits on access to a resource in an environment where there are many executing threads. In other words, locks are used to enforce concurrency control policies. Locks are vulnerable to certain problems and failures. One such problem is deadlock, where each of two threads waits for a lock that the other thread holds and will not proceed until it has acquired the lock. Consequently, unless something is done, both threads will wait forever for each other.
In a conventional single threaded computing system, a single thread can lock and unlock the same lock in the same thread so that no deadlock problem will occur. On the other hand, in a more sophisticated multi-threaded computing system, deadlocks can occur when more than one thread need to acquire the same lock. For example, one common source of deadlock is the following scenario. Two threads t—1 and t—2 share a set of common resources R by taking a lock L before accessing any of the resources in R and releasing it when done with that resource. Consider the case where thread t—1 takes lock L to access resource r—1 in R, and then waits on thread t—2 to perform a task. Deadlock occurs if thread t—2 must take lock L to access resource r—2 in R before it can finish. In that situation, thread t—1 waits for thread t—2 to finish, while thread t—2 waits for thread t—1 to release lock L. They will both wait forever and not make any further progress, resulting in a deadlock.
The standard solution to this problem is create two locks L—1 and L—2 and split the set of resources R into two groups R—1 and R—2 controlled by these two different locks, making sure r—1 is a member of R—1 and r—2 is a member of R—2. Now thread t—1 takes lock L—1 to access r—1 and waits on thread t—2. Thread t—2 takes lock L—2 to access r—2. Thread t—2 successfully completes its transaction, so now thread t—1 can also proceed. This resolves the deadlock. However, for a large, existing piece of software, correctly dividing resources originally synchronized by a single lock into two groups synchronized by separate locks requires a significant and often overly costly engineering effort.
In summary, deadlock can easily occur when two threads accessing separate resources must cooperate but these separate resources are accessed under the same lock. Re-engineering the software so that these separate resources are accessed under separate locks may be too costly if the software is very complex. Therefore, what is desired is an invention to avoid deadlock and costly re-engineering of software.